package com.sort;

import java.util.Arrays;

/**
 * Shell排序
 *
 * @author zhongyi_yang
 */
public class ShellSort {
	/**
	 * Shell排序
	 *
	 * @param dataWraps
	 */
	public static void shellSort(DataWrap[] dataWraps) {
		System.out.println("开始排序：");
		int arrayLength = dataWraps.length;
		// h保存可变增量
		int h = 1;
		// 按h*3+1得到增量序列的最大值
		while (h <= arrayLength / 3) {
			h = h * 3 + 1;
		}
		while (h > 0) {
			System.out.println("===h的值:" + h + "===");
			for (int i = h; i < arrayLength; i++) {
				// 当整体后移时，保证dataWraps[i]的值不会丢失
				DataWrap tmpDataWrap = dataWraps[i];
				// i索引处的值已经比前面的所有制都大，表明已经有序，无须插入
				// （i-1索引之前的数据已经有序，i-1索引处元素的值就是最大值）
				if (dataWraps[i].compareTo(dataWraps[i - h]) < 0) {
					int j = i - h;
					// 整体后移h格
					for (; j >= 0 && dataWraps[j].compareTo(tmpDataWrap) > 0; j -= h) {
						dataWraps[j + h] = dataWraps[j];
					}
					// 最后将tmpDataWraps的值插入合适位置
					dataWraps[j + h] = tmpDataWrap;
				}
				System.out.println(Arrays.toString(dataWraps));
			}
			h = (h - 1) / 3;
		}
	}

	public static void main(String[] args) {
		DataWrap dataWrap[] = {new DataWrap(9, ""), new DataWrap(-16, ""),
				new DataWrap(21, "*"), new DataWrap(23, ""),
				new DataWrap(-30, ""), new DataWrap(-49, ""),
				new DataWrap(21, ""), new DataWrap(30, "*"),
				new DataWrap(13, "*")};
		System.out.println("排序前：" + Arrays.toString(dataWrap));
		shellSort(dataWrap);
		System.out.println("排序后：" + Arrays.toString(dataWrap));
	}
}
